package com.sise.Tree;

/**
 *      题目：110. 平衡二叉树
 *
 *      给定一个二叉树，判断它是否是高度平衡的二叉树。
 *      本题中，一棵高度平衡二叉树定义为：
 *      一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
 *
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：true
 *
 *      解题思路（递归三部曲）：
 *      1、终止条件；
 *      2、返回什么信息；
 *      3、本级递归应该做什么；
 */
public class _110_isBalanced {
    public boolean isBalanced(TreeNode root) {
        // 自顶向下
//        return height(root) >= 0;

        // 自底向上
        return recur(root) != -1;
    }

    /**
     * <自顶向下递归>
     *      解题思路（递归三部曲）：
     *      1、终止条件：当输入值为 null，说明是底节点，没有左右子树的它 自然就是平衡二叉树了
     *      2、返回什么信息：输入值往往是 root.left 或 root.right，返回给上一级节点的值为当前节点的高度 height。如果此树已经失衡，那么在 leftHeight >= 0 && rightHeight >= 0 判断时，
     *                    会一直返回 -1 直到最顶层
     *      3、本级递归应该做什么：计算左右子树的层数相差是否 小于1，如果平衡的话，那么返回左右子树中最高层的 height
     *
     *  总结：输入当前节点 root，分别获取其左右子节点的高度，通过高度相减的值是否 小于等于一，判断其是否失衡
     */
    private int height(TreeNode root) {
        if (root == null) return 0;

        // 获取当前节点的左右子节点的最大高度
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // 如果此树已经失衡，那么在 leftHeight >= 0 && rightHeight >= 0 判断时，会一直返回 -1 直到最顶层
        if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1){

            // 本次递归所做的事情：在左右子节点中挑选出最高值，再加上当前节点 root 的高度，故此是 max + 1
            return Math.max(leftHeight, rightHeight) + 1;
        }else {
            return -1;
        }
    }


    /**
     *  <自底向上递归 - 提前阻断>
     *      思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
     *      1、递归返回值：
     *          当节点root 左 / 右子树的高度差 <2 ：则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1 （ max(left, right) + 1 ）；
     *          当节点root 左 / 右子树的高度差 ≥2 ：则返回 -1 ，代表 此子树不是平衡树。
     *      2、递归终止条件：
     *          当越过叶子节点时，返回高度 0 ；
     *          当左（右）子树高度 left== -1 时，代表此子树的 左（右）子树 不是平衡树，因此直接返回 -1 ；
     *
     *      复杂度分析：
     *          时间复杂度 O(N)： NN 为树的节点数；最差情况下，需要递归遍历树的所有节点。
     *          空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N)的栈空间。
     *
     */
    private int recur(TreeNode root){

        // 如果 root 为空说明到达底部，那么返回高度为 0
        if (root == null) return 0;

        // 前序遍历到最底层，然后开始自底向上。这里会进行多次 if 的失衡判断，如果左右子节点为 -1，那么就一直向上 return -1
        int left = recur(root.left);
        if (left == -1) return -1;

        int right = recur(root.right);
        if (right == -1) return -1;

        // 如果 左子树高度 和 右子树 的高度大于2，那么说明此书失衡，向上 return -1
        if (Math.abs(left - right) > 2){
            return -1;
        }

        // 返回值为最高层数，
        return Math.max(left, right) + 1;
    }
}
